package leetcode39

func combinationSum(candidates []int, target int) [][]int {
	res := make([][]int, 0)
	var dfs func(target, idx int)

	comb := []int{}

	dfs = func(target, idx int) {
		// 超出直接返回
		if idx == len(candidates) {
			return
		}
		if target == 0 {
			res = append(res, comb)
			return
		}
		dfs(target, idx+1)
		if target-candidates[idx] >= 0 {
			comb = append(comb, candidates[idx])
			dfs(target-candidates[idx], idx)
			comb = comb[:len(comb)-1]
		}
	}
	dfs(target, 0)
	return res
}
